<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
</head>

<body></body>
<script>
    /*
        链表存储有序的元素集合，其内存不是连续的，每个元素由存储元素本身的节点和一个指向下个元素的引用（也称之为指针和链接）组成。
        好处：
            增删元素的时候不需要移动其他元素。适合存储，不适合查询。
        注意：
            需要使用指针；
            访问元素，需要从表头（起点）开始迭代链表知道找到为止。

    */
    //    辅助函数
    function defaultEquals(a, b) {
        return a === b; // 比较元素是否相等
    }
    function isNullOrUndefined(ele) {
        if (ele === void 0 || ele === null) {
            return true;
        }
        return false;
    }
    // 辅助类
    class NodeHelp {
        constructor(ele, next = void 0) {
            this.element = ele;
            this.next = next;
        }
    }
    // 链表骨架
    class LinkedList {
        #count = 0; // 存储元素数量
        #head = void 0; // 链表头元素
        constructor(
            equalsFn = defaultEquals,
            isNullOrUndefine = isNullOrUndefined
        ) {
            this.equalsFn = equalsFn;
            this.isNullOrUndefine = isNullOrUndefined;
        }
        // 链表尾部添加元素
        push(element) {
            const node = new NodeHelp(element);
            let current;
            if (this.isNullOrUndefine(this.#head)) {
                // 如果头元素为空，添加元素后，头元素就是这个被添加进来的元素
                this.#head = node;
            } else {
                // 如果头元素非空
                // 那么就找头元素指向的下个元素，直到如果下个元素是空的时候，把新元素插到这个元素的后面
                current = this.#head; // 此时是 Node 类，先把
                while (!this.isNullOrUndefine(current.next)) {
                    current = current.next; // 在这里，current 最终会是链表最后一个元素
                }
                current.next = node; // 之后最后一个元素的后面就是 node
            }
            this.#count++;
        }
        // 获取特定位置某处元素
        getElementAt(index) {
            // 检查不合理值
            if (
                typeof index != "number" ||
                Number.isNaN(index) ||
                !Number.isFinite(index)
            ) {
                throw new Error("输入位置必须是具体的数字形式！");
            }
            if (this.#count === 0) {
                return null;
            }
            if (index < 0 || index >= this.#count) {
                throw new Error("输入位置必须大于等于 0，且不能超过链表长度！");
            }
            let node = this.#head;
            for (let i = 0; i < index; i++) {
                node = node.next; // 更新当前元素
            }
            return node;
        }
        // 从链表特定位置移除元素，返回被移除元素
        removeAt(index) {
            // 检查不合理值
            if (
                typeof index != "number" ||
                Number.isNaN(index) ||
                !Number.isFinite(index)
            ) {
                throw new Error("输入位置必须是具体的数字形式！");
            }
            if (this.#count === 0) {
                return null;
            }
            if (index < 0 || index >= this.#count) {
                throw new Error("输入位置必须大于等于 0，且不能超过链表长度！");
            }
            let current = this.#head; // 记录当前头部元素
            if (index === 0) {
                // 获取头元素
                this.#head = current.next;
            } else {
                let previous = this.getElementAt(index - 1); // 记录前一个元素
                current = previous.next; // 待删除项
                // 跳出循环后，previous 是对应的前一项；current是后一项（待删除项）；current.next 是待删除项的下一项
                // 所以如果需要删除待删项，那么就需要把前一项和待删项的后一项捏合在一起，使得前一项的指针指向待删项的后一项
                previous.next = current.next;
            }
            this.#count--;
            return current.element;
        }
        // 在任意项前面插入
        insert(el, index) {
            // 检查不合理值
            if (
                typeof index != "number" ||
                Number.isNaN(index) ||
                !Number.isFinite(index)
            ) {
                throw new Error("输入位置必须是具体的数字形式！");
            }
            if (index < 0 || index > this.#count) {
                throw new Error("输入位置必须大于等于 0，且不能超过链表长度！");
            }
            const node = new NodeHelp(el);
            if (index === 0) {
                const current = this.#head;
                node.next = this.#head;
                this.#head = node; // 讲链表的头部设置为 node
            } else {
                const previous = this.getElementAt(index - 1);
                const current = previous.next;
                node.next = current;
                previous.next = node;
            }
            this.#count++;
        }
        // 是否为空链表
        isEmpty() {
            return this.#count === 0;
        }
        // 链表长度
        size() {
            return this.#count;
        }
        // 获取头元素
        getHead() {
            return this.#head;
        }
        toString() {
            if (this.isNullOrUndefine(this.#head)) {
                return "{}";
            }
            let str = "{";
            for (let i = 0; i < this.#count; i++) {
                str += `${i}: ${this.getElementAt(i).element}, `;
            }
            str = str.slice(0, str.length - 2);
            return str + "}";
        }
    }
    let y = new LinkedList();
    y.push({
        o: 9,
    });
    y.push(13);
    y.insert(111, 1);
    console.log(y.toString());

    // 双向链表辅助类
    class DoublyNodeHelp extends NodeHelp {
        constructor(element, next, prev) {
            super(element, next); // super 指向父类，相当于 this
            this.prev = prev;
        }
    }
    // 双向链表
    // 提供了两种迭代方式，从头到尾和从尾到头，也就是一个元素有双指针
    class DoublyLinkedList extends LinkedList {
        #tails = void 0 // 链表尾元素
        constructor(equalsFn = defaultEquals) {
            super(equalsFn) // 初始化父类中的 equalsFn、#count、#head
        }
    }
    let r = new DoublyLinkedList();
    r.push("o")
    console.log(r);
</script>

</html>